package classic;

import java.util.LinkedList;

/**
 * 根据入栈顺序和出栈顺序，判断是否对应同一个栈
 *
 * @author zj
 */
public class DetermineStack {


    public static void main(String[] args) {
        int in[] = {1, 2, 3, 4, 5};
        //int out[] = {4, 3, 5, 1, 2};
        int out[] = {4, 3, 5, 2, 1};
        //int out[] = {4, 5, 3, 2, 1};
        System.out.println(validate(in, out));
    }

    public static boolean validate(int in[], int out[]) {
        //辅助栈，用来保存每一步的入栈序列
        LinkedList<Integer> s = new LinkedList<Integer>();
        int inIndex = 0; //遍历入栈序列的指针
        int outIndex = 0; //遍历出栈序列的指针
        while (outIndex < out.length) {
            int current = out[outIndex];
            if (!s.isEmpty() && s.peek() == current) {
                s.pop();
                outIndex++;
            } else {
                if (inIndex >= in.length) {
                    return false;
                } else {
                    s.push(in[inIndex]);
                    inIndex++;
                }
            }
        }
        return true;
    }
}
